"""
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:

如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-ladder
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。

"""

"""
图的问题，层级遍历

如果满足条件放在队列中，
不访问访问过的节点
"""

# 超时
from typing import List
from collections import deque, defaultdict

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        L = len(beginWord)
        all_combo_dict = defaultdict(list)
        for word in wordList:
            for i in range(L):
                all_combo_dict[word[:i] + "*" + word[i+1:]].append(word)
        
        d = deque()
        d.append((beginWord, 1))
        visited = {}
        while d:
            word1, step = d.pop()

            for i in range(L):
                combo_word = word1[:i] + "*" + word1[i+1:]
                words = all_combo_dict.get(combo_word, [])
                for word in words:
                    if word1 == endWord:
                        return step
                    if word not in visited:
                        d.appendleft((word, step+1))
                        visited[word] = True

        else: # 这点没考虑到，需要返回0
            return 0

if __name__ == "__main__":
    r = Solution().ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"])
    # r = Solution().ladderLength("hot", "dog", ["hot","dog"])
    print(r)


